package newcoder_exp.justPractise;
import java.util.*;
import graph.*;

public class Pra4_Djistra {
    
    //最短路径
    /* 
        head为出发节点
        返回为每个Node到head的最短路径长度
     */
    public Map<Node<Integer>, Integer> shortestPath(Graph<Integer> g, Node<Integer> head) {
        //若不存在该Node对应的key，即表示距离为无穷大
        Map<Node<Integer>, Integer> path = new HashMap<>();
        int curDistance = 0;//当前更新到节点的距离（作为基础去更新其他节点的最短路径长度）
        Set<Node<Integer>> visited = new HashSet<>(); //已经求得最短路径的节点
        path.put(head, 0); //head到自己的最短路径为0
        Node<Integer> curNode = head;
        visited.add(head);
        while (curNode != null) { //set中已经添加了所有节点
            for (Edge<Integer> edge: curNode.edges) { //刷新最短路径
                if (path.containsKey(edge.out)) {
                    path.put(edge.out, Math.min(path.get(edge.out), curDistance + edge.weight));
                } else {
                    path.put(edge.out, curDistance + edge.weight);
                }
            }
            //找到下个遍历的节点
            curNode = getUnvisitedNearestNode(path, visited);
            curDistance += path.get(curNode);
        }
        return path;
    }

    public Node<Integer> getUnvisitedNearestNode(Map<Node<Integer>, Integer> path, Set<Node<Integer>> visited) {
        Node<Integer> res = null;
        int min = Integer.MAX_VALUE;
        for (Node<Integer> node: path.keySet()) {
            if (!visited.contains(node) && (res == null || path.get(node) < min)) {
                min = path.get(node);
                res = node;
            }
        }
        return res;
    }

}
